package class07;

/**
 * @description: https://leetcode.com/problems/path-sum/
 * @time: 2021/7/17 13:07
 * @author: lhy
 */
public class PathSum {
    public static boolean isSum = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        isSum = false;
        process(root,0,targetSum);
        return isSum;
    }
    private void process(TreeNode root,int preSum,int targetSum){
        if (root.left == null && root.right == null) {
            if (root.val + preSum == targetSum){
                isSum = true;
            }
            return;
        }
        preSum += root.val;
        if (root.left != null) {
            process(root.left,preSum,targetSum);
        }
        if (root.right != null){
            process(root.right,preSum,targetSum);
        }
    }

    /**
     * 方法2
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return process(root,targetSum);
    }
    private boolean process(TreeNode root,int rest){
        if (root.left == null && root.right == null) {
            return root.val == rest;
        }
        boolean ans = root.left != null && process(root.left, rest - root.val);
        ans |= root.right != null && process(root.right,rest - root.val);
        return ans;
    }
}
